class Solution {
public:
  vector<string> generateParenthesis(int n) {

    vector<string> ans;

    dfs(ans, *(new string()), 0, 0, 2 * n, n);

    return ans;

  }

  void dfs(vector<string> &ans, string &temp, int left, int right, int rest, const int n){

    if(rest == 0){
      ans.push_back(temp);
      return;
    }

    if(left < n){
      temp.push_back('(');
      dfs(ans, temp, left + 1, right, rest - 1, n);
      temp.pop_back();
    }

    if(right < left){
      temp.push_back(')');
      dfs(ans, temp, left, right + 1, rest - 1, n);
      temp.pop_back();
    }

    return;

  }

};